package datastructure.sort_algorithm;

import java.util.Arrays;

/**
 * 基数排序
 * 使用空间换时间的经典算法(n*k)
 * @author lbw
 */
public class RadixSort {

    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214, -9, -85, -965, 55};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr){
        int maxDigit = getMaxDigit(arr);
        //用来进行取余操作，每次循环后乘10
        int num = 10;
        int dev = 1;
        for (int i = 0; i < maxDigit; i++){
            //定义一个二维数组,表示10个桶，每个桶就是一个一维数组
            int[][] bucket = new int[19][arr.length];
            //为了记录每个桶中，实际存放了多少个数据，定义一个一维数组记录各个桶每次放入的个数
            int[] bucketElementCounts = new int[19];
            //将数放入桶中
            for (int j = 0; j < arr.length; j++){
                int digit = ((arr[j] % num) / dev) + 10;
                bucket[digit][bucketElementCounts[digit]] = arr[j];
                bucketElementCounts[digit]++;
            }
            //将数从桶中取出放入数组
            int index = 0;
            for (int m = 0; m < bucketElementCounts.length; m++){
                for (int n = 0; n < bucketElementCounts[m]; n++){
                    arr[index++] = bucket[m][n];
                }
            }
            num = num * 10;
            dev = dev * 10;
        }

    }

    public static int getMaxDigit(int[] arr){
        int maxValue = getMaxValue(arr);
        return getLength(maxValue);
    }

    public static int getLength(int num){
        if (num == 0){
            return 1;
        }
        int length = 0;
        for (int temp = num; temp != 0; temp /= 10){
            length++;
        }
        return length;
    }

    public static int getMaxValue(int[] arr){
        int maxValue = 0;
        for (int i : arr) {
            if (i > maxValue){
                maxValue = i;
            }
        }
        return maxValue;
    }
}
